/*编写程序，实现重新排列九宫格（即在3X3的几个格子上填1~9的数字，使每行、每列、每对角三个数之和都是15）。
然后，查阅资料，了解世界最难、最大九宫格游戏，您能够给出答案吗？*/

//我查阅资料后发现世界上目前没有统一理论标准可评价出最难、最大九宫格游戏

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

int a[3][3];
int cnt = 0;
_Bool vis[10];

_Bool check()
{
    int i,j;
    _Bool f = 1;
    for(j=0; j < 3 && f;j++)
    {
        int s = 0;
        for(i = 0;i < 3;i++)
            s += a[i][j];
        if(s != 15)
            f = 0;
    }
    if(!(a[0][0] + a[1][1] + a[2][2] == 15 && a[0][2] + a[1][1] + a[2][0] == 15))
        f = 0;
    return f;
}

void print()
{
    int i,j;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            printf("%d%c",a[i][j],j==2?'\n':' ');
    puts("");
    cnt++;
}
void dfs(int c,int r)
{
    if(c==3)
    {
        if(check())
            print();
        return;
    }
    if(c==1&&r==1)
        dfs(c,r+1);
    else{
        int i;
        for(i=1;i<=9;i++)
            if(!vis[i])
            {
                vis[i]=1;
                a[c][r]=i;
                if(r==2)
                {
                    if(a[c][0]+a[c][1]+a[c][2]!=15)
                    {
                        a[c][r]=0;
                        vis[i]=0;
                        continue;
                    }
                    dfs(c+1,0);
                }
                else
                    dfs(c,r+1);
                a[c][r]=0;
                vis[i]=0;
            }
    }

}
int main()
{
    memset(a,0,sizeof(a));
    memset(vis,0,sizeof(vis));
    a[1][1] = 5;
    vis[5] = 1;
    dfs(0, 0);
    printf("%d solutions in total.\n",cnt);
    return 0;
}